package com.datastructure3.binarytree;

import com.datastructure.array.Utils;
import com.sun.xml.internal.ws.util.Pool;
import org.junit.Test;
import org.omg.PortableServer.POA;
import sun.reflect.generics.tree.Tree;
import sun.util.logging.PlatformLogger;

import javax.sound.sampled.LineListener;
import java.util.*;

/**
 * @author: 临晖
 * @since: 2024-07-31
 */
public class Solution {


    /**
     * 144. 二叉树的前序遍历
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历
     * <p>
     * 中 左 右
     *
     * @param root
     * @return
     */
    public List<Integer> preorderTraversal(TreeNode root) {
        //方式一： 递归
        //List<Integer> res = new ArrayList<>();
        //preorder(root, res);
        //return res;

        //方式二： 迭代
        List<Integer> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            //输出中间节点
            res.add(node.val);

            if (node.right != null) {
                stack.push(node.right);
            }

            if (node.left != null) {
                stack.push(node.left);
            }
        }

        return res;
    }

    public void preorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }

        list.add(root.val);

        preorder(root.left, list);
        preorder(root.right, list);
    }


    /**
     * 145. 二叉树的后序遍历
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历
     *
     * @param root
     * @return
     */
    public List<Integer> postorderTraversal(TreeNode root) {
        //方式一
        //List<Integer> res = new ArrayList<>();
        //postorder(root, res);
        //return res;


        //方式二： 迭代
        List<Integer> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            //输出中间节点
            res.add(node.val);

            if (node.left != null) {
                stack.push(node.left);
            }

            if (node.right != null) {
                stack.push(node.right);
            }
        }
        Collections.reverse(res);
        return res;
    }

    public void postorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }


        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);
    }


    /**
     * 94. 二叉树的中序遍历
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
     * <p>
     * 左 中 右
     *
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        //方式一： 递归
        //List<Integer> res = new ArrayList<>();
        //inorder(root, res);
        //return res;

        //方式二： 迭代
        List<Integer> res = new ArrayList<>();

        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp = root;
        while (temp != null || !stack.isEmpty()) {

            if (temp != null) {
                stack.push(temp);
                temp = temp.left;
            } else {

                TreeNode node = stack.pop();

                res.add(node.val);

                if (node.right != null) {
                    temp = node.right;
                }
            }
        }

        return res;
    }


    public void inorder(TreeNode root, List<Integer> list) {
        if (root == null) {
            return;
        }


        inorder(root.left, list);
        inorder(root.right, list);
        list.add(root.val);
    }


    /**
     * 102. 二叉树的层序遍历
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            ArrayList<Integer> tempList = new ArrayList<>();
            while (size-- > 0) {
                TreeNode node = queue.removeLast();
                tempList.add(node.val);

                if (node.left != null) {
                    queue.push(node.left);
                }

                if (node.right != null) {
                    queue.push(node.right);
                }

            }
            res.add(tempList);

        }
        return res;

    }


    /**
     * 107. 二叉树的层序遍历 II
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        queue.push(root);

        while (!queue.isEmpty()) {
            int len = queue.size();

            List<Integer> tempList = new ArrayList<>();
            while (len-- > 0) {
                TreeNode temp = queue.removeLast();
                tempList.add(temp.val);

                if (temp.left != null) {
                    queue.push(temp.left);
                }

                if (temp.right != null) {
                    queue.push(temp.right);
                }

            }
            res.add(tempList);
        }

        Collections.reverse(res);

        return res;
    }


    /**
     * 199. 二叉树的右视图
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
     *
     * @param root
     * @return
     */
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();

        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(root);

        while (!queue.isEmpty()) {
            int len = queue.size();

            while (len-- > 0) {
                TreeNode node = queue.removeLast();

                if (len == 1) {
                    res.add(node.val);
                }

                if (node.left != null) {
                    queue.push(node.left);
                }

                if (node.right != null) {
                    queue.push(node.right);
                }
            }

        }

        return res;

    }


    /**
     * 637. 二叉树的层平均值
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
     *
     * @param root
     * @return
     */
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();

        if (root == null) {
            return res;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(root);

        while (!queue.isEmpty()) {
            int len = queue.size();
            int count = len;
            double sum = 0;

            while (len-- > 0) {
                TreeNode node = queue.removeLast();

                sum += node.val;

                if (node.left != null) {
                    queue.push(node.left);
                }

                if (node.right != null) {
                    queue.push(node.right);
                }
            }
            res.add(sum / count);
        }

        return res;
    }


    /**
     *
     * 429. N 叉树的层序遍历
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
     * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
     *
     * @param root
     * @return
     */
    //public List<List<Integer>> levelOrder(Node root) {
    //    List<List<Integer>> res = new ArrayList<>();
    //
    //    if (root == null) {
    //        return res;
    //    }
    //
    //    LinkedList<Node> queue = new LinkedList<>();
    //    queue.push(root);
    //
    //    while (!queue.isEmpty()) {
    //        int size = queue.size();
    //        ArrayList<Integer> tempList = new ArrayList<>();
    //
    //        while (size-- > 0) {
    //            Node node = queue.removeLast();
    //            tempList.add(node.val);
    //
    //            for (int i = 0; i < node.children.size(); i++) {
    //                queue.push(node.children.get(i));
    //            }
    //        }
    //
    //        res.add(tempList);
    //
    //    }
    //
    //    return res;
    //}
    //class Node {
    //    public int val;
    //    public List<Node> children;
    //
    //    public Node() {
    //    }
    //
    //    public Node(int _val) {
    //        val = _val;
    //    }
    //
    //    public Node(int _val, List<Node> _children) {
    //        val = _val;
    //        children = _children;
    //    }
    //}


    /**
     * 515. 在每个树行中找最大值
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。
     *
     * @param root
     * @return
     */
    public List<Integer> largestValues(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();


        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            int maxNum = Integer.MIN_VALUE;

            while (size-- > 0) {
                TreeNode node = queue.removeLast();
                maxNum = Math.max(maxNum, node.val);

                if (node.left != null) {
                    queue.push(node.left);
                }

                if (node.right != null) {
                    queue.push(node.right);
                }
            }

            res.add(maxNum);
        }

        return res;
    }


    /**
     * 116. 填充每个节点的下一个右侧节点指针
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
     *
     * @param root
     * @return
     */
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }


        LinkedList<Node> queue = new LinkedList<>();
        queue.push(root);


        while (!queue.isEmpty()) {
            int size = queue.size();

            //定义快慢节点
            Node slowNode = null;
            while (size-- > 0) {
                Node node = queue.removeLast();

                node.next = slowNode;
                slowNode = node;

                if (node.right != null) {
                    queue.push(node.right);
                }

                if (node.left != null) {
                    queue.push(node.left);
                }
            }
        }

        return root;

    }


    /**
     * 104. 二叉树的最大深度
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个二叉树 root ，返回其最大深度。
     * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        //方式一： 广度遍历
        //if (root == null) {
        //    return 0;
        //}
        //
        //LinkedList<TreeNode> queue = new LinkedList<>();
        //queue.push(root);
        //
        //int res = 0;
        //while (!queue.isEmpty()) {
        //    int size = queue.size();
        //    res++;
        //    while (size-- > 0) {
        //        TreeNode node = queue.removeFirst();
        //        if (node.left != null) {
        //            queue.push(node.left);
        //        }
        //
        //        if (node.right != null) {
        //            queue.push(node.right);
        //        }
        //    }
        //}
        //
        //return res;

        //方式二：深度遍历

        if (root == null) {
            return 0;
        }

        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return left > right ? left + 1 : right + 1;
    }


    /**
     * 111. 二叉树的最小深度
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个二叉树，找出其最小深度。
     * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
     * 说明：叶子节点是指没有子节点的节点。
     *
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        //方式一：深度遍历：递归
        //if (root == null) {
        //    return 0;
        //}
        //if (root.left == null && root.right == null) {
        //    return 1;
        //}
        //
        //int left = Integer.MAX_VALUE;
        //int right = Integer.MAX_VALUE;
        //if (root.left != null){
        //    left = minDepth(root.left);
        //}
        //
        //if (root.right != null) {
        //    right = minDepth(root.right);
        //
        //}
        //
        //return left < right ? left + 1: right + 1;

        if (root == null) {
            return 0;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(root);
        int res = 0;

        a:
        while (!queue.isEmpty()) {
            int size = queue.size();
            res++;
            b:
            while (size-- > 0) {
                TreeNode node = queue.removeLast();

                if (node.left != null) {
                    queue.push(node.left);
                }

                if (node.right != null) {
                    queue.push(node.right);
                }

                if (node.left == null && node.right == null) {
                    break a;
                }
            }
        }

        return res;
    }


    /**
     * 226. 翻转二叉树
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点
     *
     * @param root
     * @return
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }

        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        //交换
        root.left = right;
        root.right = left;

        return root;
    }


    /**
     * 101. 对称二叉树
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     *
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        //递归
        //if (root == null) {
        //    return true;
        //}
        //
        //return isSymmetric_(root.left, root.right);

        //迭代
        if (root == null) {
            return true;
        }

        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(root.left);
        queue.push(root.right);

        while (!queue.isEmpty()) {
            TreeNode root1 = queue.removeLast();
            TreeNode root2 = queue.removeLast();

            if (root1 == null && root2 != null) {
                return false;
            } else if (root1 != null && root2 == null) {
                return false;
            } else if (root1 == null && root2 == null) {
                return true;
            } else if (root1.val != root2.val) {
                return false;
            }

            queue.push(root1.left);
            queue.push(root2.right);

            queue.push(root1.right);
            queue.push(root2.left);
        }

        return true;
    }

    public boolean isSymmetric_(TreeNode root1, TreeNode root2) {
        //判断逻辑
        if (root1 != null && root2 == null) {
            return false;
        } else if (root1 == null && root2 != null) {
            return false;
        } else if (root1 == null && root2 == null) {
            return true;
        } else {
            if (root1.val == root2.val) {
                return isSymmetric_(root1.left, root2.right) && isSymmetric_(root1.right, root2.left);
            } else {
                return false;
            }
        }

    }


    /**
     * 100. 相同的树
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     *
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q != null) {
            return false;
        } else if (p != null && q == null) {
            return false;
        } else if (p == null && q == null) {
            return true;
        } else {
            if (p.val == q.val) {
                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            } else {
                return false;
            }
        }

    }


    /**
     * 572. 另一棵树的子树
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
     * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
     *
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        } else if (root == null && subRoot != null) {
            return false;
        }

        return isSubtree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }


    /**
     * 222. 完全二叉树的节点个数
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
     * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
     * 若最底层为第 h 层，则该层包含 1~ 2h 个节点。
     *
     * @param root
     * @return
     */
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return countNodes(root.left) + countNodes(root.right) + 1;
    }


    /**
     * 110. 平衡二叉树
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定一个二叉树，判断它是否是
     * 平衡二叉树
     * <p>
     * <p>
     * public boolean isBalanced(TreeNode root) {
     * if (root == null) {
     * return true;
     * }
     * <p>
     * if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1) {
     * return false;
     * } else {
     * return isBalanced(root.left) && isBalanced(root.right);
     * }
     * }
     * <p>
     * public int getDepth(TreeNode root){
     * if (root == null){
     * return 0;
     * }
     * <p>
     * int left = getDepth(root.left);
     * int right = getDepth(root.right);
     * <p>
     * return left > right ? left + 1 : right + 1;
     * }
     * 以上是自己写的，以下是看解析写的；
     * 问题：
     * 为什么自己的思路一开始不是下面那么简洁？
     * 自己思考过程：
     * 首先自己一开始想到了需要求树的最大深度。而树的最大深度返回的是int类型；
     * 如果在求最大深度过程中判断左右子树相差是否大于一，那么需要返回true 或 false，
     * 这与求最大深度返回的int类型相冲突，一个函数不可能既返回boolean类型，又返回int类型，所以经过思考，
     * 有了如上思路。而一开始只想到了最外面的左右子树，却面向到子树的子树，因此写了:
     * *         if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1) {
     * *             return false;
     * *         } else {
     * *             return true;
     * *         }
     * 但这样肯定是不对的，还需要考虑树的子树左右是否平衡，于是有了继续递归：
     * *         if (Math.abs(getDepth(root.left) - getDepth(root.right)) > 1) {
     * *             return false;
     * *         } else {
     * *             return isBalanced(root.left) && isBalanced(root.right);
     * *         }
     * 而以上就是自己的思路；
     * 而经过看解析后了解到了：
     * 一个函数是不可以同时返回boolean类型和int类型，但是，我们可以通过区分在不同区域的int类型来同时表示boolean类型；
     * 比如说：小于零（即-1）表示false，大于等于0表示true
     * 因此这样就可以在求左右子树的深度的同时来进行判断是否平衡，如果平衡那么返回其子树的最大深度（即表示true），如果不平衡，那么返回-1（即表示false）
     *
     * @param root
     * @return
     */
    //todo 重点回忆
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        return !(getDepth(root) == -1);
    }

    public int getDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = getDepth(root.left);
        int right = getDepth(root.right);

        if (Math.abs(left - right) > 1 || left == -1 || right == -1) {
            return -1;
        }

        return left > right ? left + 1 : right + 1;
    }


    /**
     * 257. 二叉树的所有路径
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
     * 叶子节点 是指没有子节点的节点。
     *
     * @param root
     * @return
     */
    public List<String> binaryTreePaths(TreeNode root) {
        ArrayList<String> res = new ArrayList<>();
        pre(root, root.val + "", res);
        return res;
    }

    public void pre(TreeNode node, String path, List<String> res) {
        if (node.left == null && node.right == null) {
            res.add(path);
            return;
        }
        //if (node == null) {
        //    return;
        //}
        //中
        //int len = -1;
        if (node.left != null) {
            pre(node.left, path + "->" + node.left.val, res);
            //len = ("->" + node.left.val).length();
        }
        if (node.right != null) {
            pre(node.right, path + "->" + node.right.val, res);
        }

    }


    /**
     * 404. 左叶子之和
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定二叉树的根节点 root ，返回所有左叶子之和。
     *
     * @param root
     * @return
     */
    public int sumOfLeftLeaves(TreeNode root) {
        if (root.left == null && root.right == null) {
            return 0;
        }

        return sumOfLeft(root, true);
    }

    public int sumOfLeft(TreeNode root, boolean flag) {
        if (root.left == null && root.right == null) {
            if (flag) {
                return root.val;
            } else {
                return 0;
            }
        }

        //中

        //
        int left = 0;
        int right = 0;

        if (root.left != null) {

            left = sumOfLeft(root.left, true);
        }
        if (root.right != null) {
            right = sumOfLeft(root.right, false);
        }


        return left + right;
    }


    /**
     * 513. 找树左下角的值
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。
     * 假设二叉树中至少有一个节点。
     *
     * @param root
     * @return
     */
    public int findBottomLeftValue(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(root);

        int res = 0;
        while (!queue.isEmpty()) {

            TreeNode node = queue.removeLast();
            res = node.val;

            if (node.right != null) {
                queue.push(node.right);
            }

            if (node.left != null) {
                queue.push(node.left);
            }

        }

        return res;
    }


    /**
     * 112. 路径总和
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
     * 叶子节点 是指没有子节点的节点。
     *
     * @param root
     * @param targetSum
     * @return
     */
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }

        return hasPath(root, targetSum);
    }

    public boolean hasPath(TreeNode root, int targetSum) {
        targetSum -= root.val;

        if (root.left == null && root.right == null) {
            if (targetSum == 0) {
                return true;
            }
            return false;
        }

        boolean left = false;
        boolean right = false;
        if (root.left != null) {
            left = hasPath(root.left, targetSum);
        }

        if (root.right != null) {
            right = hasPath(root.right, targetSum);
        }

        return left || right;

    }


    /**
     * 113. 路径总和 II
     * 尝试过
     * 中等
     * 相关标签
     * 相关企业
     * 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
     * 叶子节点 是指没有子节点的节点。
     *
     * @param root
     * @param targetSum
     * @return
     */
    List<List<Integer>> res = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return res;
        }

        path(root, targetSum, new ArrayList<>());
        return res;
    }

    public void path(TreeNode root, int target, List<Integer> path) {
        target -= root.val;
        path.add(root.val);


        if (root.left == null && root.right == null) {
            if (target == 0) {
                res.add(new ArrayList<>(path));
            }

            return;
        }

        if (root.left != null) {
            path(root.left, target, path);
            path.remove(path.size() - 1);
        }

        if (root.right != null) {
            path(root.right, target, path);
            path.remove(path.size() - 1);
        }
    }


    ///**
    // * 106. 从中序与后序遍历序列构造二叉树
    // * 已解答
    // * 中等
    // * 相关标签
    // * 相关企业
    // * 给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
    // * <p>
    // * 左 右 中 postorder
    // * 左 中 右 inorder
    // *
    // * @param inorder
    // * @param postorder
    // * @return
    // */
    //public TreeNode buildTree(int[] inorder, int[] postorder) {
    //
    //    int temp = 0;
    //
    //    if (postorder.length == 0) {
    //        return null;
    //    }
    //
    //    if (postorder.length > 0) {
    //        temp = postorder[postorder.length - 1];
    //    }
    //
    //    int mid;
    //    for (mid = 0; mid < inorder.length; mid++) {
    //        if (inorder[mid] == temp) {
    //            break;
    //        }
    //    }
    //
    //    //开始切割：后续
    //    int[] leftInorder = Arrays.copyOfRange(inorder, 0, mid);
    //    int[] rightInorder = Arrays.copyOfRange(inorder, mid + 1, postorder.length);
    //
    //    //前序
    //    int[] leftPostorder = Arrays.copyOfRange(postorder, 0, leftInorder.length);
    //    int[] rightPostorder = Arrays.copyOfRange(postorder, leftInorder.length, postorder.length - 1);
    //
    //    //开始继续循环切割
    //
    //    TreeNode root = new TreeNode();
    //    root.val = temp;
    //    root.left = buildTree(leftInorder, leftPostorder);
    //    root.right = buildTree(rightInorder, rightPostorder);
    //
    //    return root;
    //}


    /**
     * 105. 从前序与中序遍历序列构造二叉树
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
     *
     * @param preorder 前序 中 左 右
     * @param inorder  中序 左 中  右
     * @return
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {


        if (preorder.length == 0) {
            return null;
        }

        //找到中间节点值
        int midNum = preorder[0];

        int midIndex;
        for (midIndex = 0; midIndex < inorder.length; midIndex++) {
            if (inorder[midIndex] == midNum) {
                break;
            }
        }

        //开始切割，中序遍历数组
        int[] leftInorder = Arrays.copyOfRange(inorder, 0, midIndex);
        int[] rightInorder = Arrays.copyOfRange(inorder, midIndex + 1, inorder.length);

        int[] leftPreorder = Arrays.copyOfRange(preorder, 1, 1 + leftInorder.length);
        int[] rightPreorder = Arrays.copyOfRange(preorder, 1 + leftInorder.length, preorder.length);

        TreeNode root = new TreeNode();
        root.val = midNum;

        root.left = buildTree(leftPreorder, leftInorder);
        root.right = buildTree(rightPreorder, rightInorder);

        return root;

    }


    /**
     * 654. 最大二叉树
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:
     * 创建一个根节点，其值为 nums 中的最大值。
     * 递归地在最大值 左边 的 子数组前缀上 构建左子树。
     * 递归地在最大值 右边 的 子数组后缀上 构建右子树。
     * 返回 nums 构建的 最大二叉树 。
     *
     * @param nums
     * @return
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {

        int maxIndx = 0;
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
                maxIndx = i;
            }
        }

        //开始切割
        int[] leftNums = Arrays.copyOfRange(nums, 0, maxIndx);
        int[] rightNums = Arrays.copyOfRange(nums, maxIndx + 1, nums.length);

        //创建节点
        TreeNode root = new TreeNode(max);
        root.left = constructMaximumBinaryTree(leftNums);
        root.right = constructMaximumBinaryTree(rightNums);

        return root;
    }


    /**
     * 617. 合并二叉树
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你两棵二叉树： root1 和 root2 。
     * 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
     * 返回合并后的二叉树。
     * 注意: 合并过程必须从两个树的根节点开始
     *
     * @param root1
     * @param root2
     * @return
     */
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }

        if (root2 == null) {
            return root1;
        }

        root1.val += root2.val;

        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);

        return root1;

    }


    /**
     * 700. 二叉搜索树中的搜索
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给定二叉搜索树（BST）的根节点 root 和一个整数值 val。
     * 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null || root.val == val) {
            return root;
        }

        if (val > root.val) {
            return searchBST(root.right, val);
        } else {
            return searchBST(root.left, val);
        }
    }

    /**
     * 98. 验证二叉搜索树
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
     * 有效 二叉搜索树定义如下：
     * 节点的左
     * 子树
     * 只包含 小于 当前节点的数。
     * 节点的右子树只包含 大于 当前节点的数。
     * 所有左子树和右子树自身必须也是二叉搜索树。
     * <p>
     * 左 中 右 - 中序遍历
     *
     * @param root
     * @return
     */
    //学到了：递归是单线程，不是多线程，是按顺序操作栈，不会同时出现同时递归到树的各个子叶的情况下
    //todo 树-递归-双指针应用
    TreeNode pre = null;

    public boolean isValidBST(TreeNode root) {

        if (root == null) {
            return true;
        }
        //左
        boolean left = isValidBST(root.left);
        //中
        if (pre != null && pre.val >= root.val) {
            return false;
        }
        pre = root;
        //右
        boolean right = isValidBST(root.right);

        return left && right;
    }

    /**
     * 530. 二叉搜索树的最小绝对差
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
     * 差值是一个正数，其数值等于两值之差的绝对值。
     *
     * @param root
     * @return
     */
    int res1 = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {

        if (root == null) {
            return -1;
        }

        getMinimumDifference(root.left);

        if (pre != null) {
            res1 = Math.min(Math.abs(pre.val - root.val), res1);
        }
        pre = root;

        getMinimumDifference(root.right);

        return res1;
    }


    /**
     * 501. 二叉搜索树中的众数
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
     * 如果树中有不止一个众数，可以按 任意顺序 返回。
     * 假定 BST 满足如下定义：
     * 结点左子树中所含节点的值 小于等于 当前节点的值
     * 结点右子树中所含节点的值 大于等于 当前节点的值
     * 左子树和右子树都是二叉搜索树
     *
     * @param root
     * @return
     */
    int count = 0;
    int max = Integer.MIN_VALUE;
    List<Integer> list = new ArrayList<>();

    public int[] findMode(TreeNode root) {

        findMode_(root);
        if (pre != null) {
            if (count == max) {
                list.add(pre.val);
            } else if (count > max) {
                list.clear();
                list.add(pre.val);
            }
        }

        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }

        return arr;
    }

    public void findMode_(TreeNode root) {
        if (root == null) {
            return;
        }

        findMode_(root.left);

        if (pre != null) {
            if (pre.val == root.val) {
                count++;
            } else if (count == max) {
                list.add(pre.val);
                count = 0;
            } else if (count > max) {
                list.clear();
                max = count;
                list.add(pre.val);
                count = 0;
            }
        }
        pre = root;

        findMode_(root.right);
    }


    /**
     * 236. 二叉树的最近公共祖先
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * <p>
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    //todo 不会
    //public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    //    if (root == null || root == p || root == q) {
    //        return root;
    //    }
    //
    //    //左
    //    TreeNode left = lowestCommonAncestor(root.left, p, q);
    //    TreeNode right = lowestCommonAncestor(root.right, p, q);
    //
    //    if (left != null && right != null) {
    //        return root;
    //    } else if (left == null && right != null) {
    //        return right;
    //    } else if (left != null && right == null) {
    //        return left;
    //    } else {
    //        return null;
    //    }
    //
    //}


    /**
     * 235. 二叉搜索树的最近公共祖先
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
     * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
     * 例如，给定如下二叉搜索树:  root = [6,2,8,0,4,7,9,null,null,3,5]
     *
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }


        TreeNode left = null;
        TreeNode right = null;

        //这里的思路是：如果都大于 或 都小于那么继续往下找，
        //如果到该结点突然发现一大一小，那么不用怀疑，这个节点就是其公共祖先节点
        if (p.val > root.val && q.val > root.val) {
            return lowestCommonAncestor(root.right, p, q);
        }

        if (p.val < root.val && q.val < root.val) {
            return lowestCommonAncestor(root.left, p, q);
        }

        return root;

    }


    /**
     * 701. 二叉搜索树中的插入操作
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
     * 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }

        ////开始遍历
        //TreeNode left = null;
        //TreeNode right = null;

        if (val < root.val) {
            root.left = insertIntoBST(root.left, val);
        }

        if (val > root.val) {
            root.right = insertIntoBST(root.right, val);
        }

        return root;
    }


    /**
     * 450. 删除二叉搜索树中的节点
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
     * 一般来说，删除节点可分为两个步骤：
     * 首先找到需要删除的节点；
     * 如果找到了，删除它。
     *
     * @param root
     * @param key
     * @return
     */
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }

        if (root.val == key && root.left == null && root.right == null) {
            return null;
        } else if (root.val == key && root.left != null && root.right != null) {
            TreeNode temp = root.right;

            while (temp.left != null) {
                temp = temp.left;
            }

            temp.left = root.left;
            return root.right;
        } else if (root.val == key && root.left != null) {
            return root.left;
        } else if (root.val == key && root.right != null) {
            return root.right;
        }


        if (key < root.val) {
            root.left = deleteNode(root.left, key);

        }

        if (key > root.val) {
            root.right = deleteNode(root.right, key);
        }

        return root;

    }


    /**
     *
     * 669. 修剪二叉搜索树
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。
     * 所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
     *
     * @param root
     * @param low
     * @param high
     * @return
     */
    //todo 不会做
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) {
            return root;
        }

        if (high < root.val) {
            return trimBST(root.left, low, high);
        }

        if (low > root.val) {
            return trimBST(root.right, low, high);
        }

        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);

        return root;

    }


    /**
     *
     * 108. 将有序数组转换为二叉搜索树
     * 已解答
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵
     * 平衡
     *  二叉搜索树。
     *
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {

        if (nums.length == 0) {
            return null;
        }

        int mid = nums.length / 2;
        TreeNode root = new TreeNode(nums[mid]);

        int[] left = Arrays.copyOfRange(nums, 0, mid);
        int[] right = Arrays.copyOfRange(nums, mid + 1, nums.length);

        root.left = sortedArrayToBST(left);
        root.right = sortedArrayToBST(right);

        return root;
    }


    /**
     *
     * 538. 把二叉搜索树转换为累加树
     * 已解答
     * 中等
     * 相关标签
     * 相关企业
     * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
     * 提醒一下，二叉搜索树满足下列约束条件：
     * 节点的左子树仅包含键 小于 节点键的节点。
     * 节点的右子树仅包含键 大于 节点键的节点。
     * 左右子树也必须是二叉搜索树。
     *
     * @param root
     * @return
     */

    public TreeNode convertBST(TreeNode root) {
        if (root == null) {
            return null;
        }

        //右
        convertBST(root.right);

        root.val += count;
        count = root.val;

        convertBST(root.left);

        return root;
    }



    @Test
    public void myTest() {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(2);

        node1.right = node2;
        node2.left = node3;
        findMode(node1);

    }
}
